package com.brett.frame.learn.tree;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Stack;

import com.brett.frame.learn.util.DataBuilder;
import com.brett.frame.learn.util.TreeBuilder;
import com.brett.frame.learn.util.TreeBuilder.TreeNode;

/**
 * 二叉树就和
 * @author lenovo
 *
 */
public class BinaryTree {
	TreeBuilder builder = new TreeBuilder();
	DataBuilder dataBuilder = new DataBuilder();
	private TreeNode root;
	private int size = 0;

	public TreeNode builder(int size) {
		int[] arr = dataBuilder.setMax(100).getDisroderArray(size);
		this.root = this.arr2Tree(arr);
		return root;
	}

	public TreeNode builder(int max, int size) {
		int[] arr = dataBuilder.setMax(max).getDisroderArray(size);
		this.root = this.arr2Tree(arr);
		return root;
	}

	public TreeNode arr2Tree(int[] arr) {
		if (arr.length < 0)
			return null;
		if (arr.length == 1) {
			root = builder.createNode(arr[0]);
			this.size++;
		}

		this.root = this.subArr2Tree(arr, 0);
		return root;
	}

	private TreeNode subArr2Tree(int[] arr, int i) {
		if (i > arr.length - 1)
			return null;
		TreeNode node = builder.createNode(arr[i]);
		this.size++;
		node.setLeftNode(subArr2Tree(arr, 2 * i + 1));
		node.setRightNode(subArr2Tree(arr, 2 * i + 2));
		return node;
	}

	public void addTail(int data) {
		if (this.root == null) {
			this.root = builder.createNode(data);
			this.size++;
		}
		ArrayDeque<TreeNode> queue = new ArrayDeque<>();
		queue.offerFirst(this.root);
		TreeNode tmp;
		while ((tmp = queue.pollLast()) != null) {
			if (tmp.getLeftNode() != null) {
				queue.offerFirst(tmp.getLeftNode());
			} else {
				tmp.setLeftNode(builder.createNode(data));
				this.size++;
				break;
			}
			if (tmp.getRightNode() != null) {
				queue.offerFirst(tmp.getRightNode());
			} else {
				tmp.setRightNode(builder.createNode(data));
				this.size++;
				break;
			}
		}
	}

	public int sum() {
		return this.subSum(0, this.root);
	}

	private int subSum(int s, TreeNode node) {
		if (node == null)
			return 0;
		s = subSum(s, node.getLeftNode());
		s += subSum(s, node.getRightNode());
		return s + node.getData();
	}

	public void preTraverse(TreeNode root) {
		System.out.println(String.format("data:%d", root.getData()));
		if (root.getLeftNode() != null)
			preTraverse(root.getLeftNode());
		if (root.getRightNode() != null)
			preTraverse(root.getRightNode());
	}

	public void preTraverseByStack(TreeNode node) {// 非递归实现
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				System.out.println(node.getData());
				stack.push(node);
				node = node.getLeftNode();
			}
			if (!stack.isEmpty()) {
				node = stack.pop();
				node = node.getRightNode();
			}
		}
	}

	public void innerTraverse(TreeNode root) {
		if (root.getLeftNode() != null)
			innerTraverse(root.getLeftNode());
		System.out.println(String.format("data:%d", root.getData()));
		if (root.getRightNode() != null)
			innerTraverse(root.getRightNode());
	}

	public void innerTraverseByStack(TreeNode node) {// 非递归实现
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.getLeftNode();
			}
			if (!stack.isEmpty()) {
				node = stack.pop();
				System.out.println(node.getData());
				node = node.getRightNode();
			}
		}
	}

	public void afterTraverse(TreeNode root) {
		if (root.getLeftNode() != null)
			afterTraverse(root.getLeftNode());
		if (root.getRightNode() != null)
			afterTraverse(root.getRightNode());
		System.out.println(String.format("data:%d", root.getData()));
	}

	public void afterTraverseByStack(TreeNode node) {// 非递归实现
		int left = 1;// 在辅助栈里表示左节点
		int right = 2;// 在辅助栈里表示右节点
		Stack<TreeNode> stack = new Stack<TreeNode>();
		Stack<Integer> stack2 = new Stack<Integer>();// 辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。

		while (node != null || !stack.isEmpty()) {
			while (node != null) {// 将节点压入栈1，并在栈2将节点标记为左节点
				stack.push(node);
				stack2.push(left);
				node = node.getLeftNode();
			}

			while (!stack.empty() && stack2.peek() == right) {// 如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
				stack2.pop();
				System.out.println(stack.pop().getData());
			}

			if (!stack.empty() && stack2.peek() == left) {// 如果是从左子节点返回父节点，则将标记改为右子节点
				stack2.pop();
				stack2.push(right);
				node = stack.peek().getRightNode();
			}

		}
	}

	public void layerTraverse(TreeNode root) {
//		ArrayDeque<TreeNode> queue=new ArrayDeque<>();
		LinkedList<TreeNode> queue = new LinkedList<>();
		if (root == null)
			return;
		queue.add(root);
		TreeNode tmp;
		while ((tmp = queue.poll()) != null) {
			System.out.println(String.format("data:%d", tmp.getData()));
			if (tmp.getLeftNode() != null)
				queue.add(tmp.getLeftNode());
			if (tmp.getRightNode() != null)
				queue.add(tmp.getRightNode());
		}
	}

	public int getSize() {
		return this.size;
	}

}
